package midalgorithms.backtrack;

import java.util.HashMap;
import java.util.HashSet;

public class _05FindWord {
    public static boolean exist(char[][] board, String word) {
        /**
         *  该算法存在问题：
         *  即不能判断出存在对应字符但不处于相邻且连续的单元格内的情况
         *  如：[["a","b"],["c","d"]]
         *      "abcd"
        HashMap<Character,Integer> hashMap = new HashMap<>();
        for (int i = 0;i < board.length;i++){
            for (int j = 0;j < board[i].length;j++){
                hashMap.put(board[i][j],hashMap.getOrDefault(board[i][j],0)+1);
            }
        }
        for (int i = 0;i < word.length();i++){
            //  如果哈希表中存在该元素，且对应的value值大于0，则将value值-1
            if (hashMap.containsKey(word.charAt(i)) && hashMap.get(word.charAt(i)) > 0){
                hashMap.put(word.charAt(i),hashMap.get(word.charAt(i)) - 1);
            }else {
                return false;
            }
        }
        return true;
        */

        for (int i = 0;i < board.length;i++){
            for (int j = 0;j < board[i].length;j++){
                //  如果基于当前元素的深度优先遍历没有结果时
                //  应该跳过当前元素，去遍历下一元素
                HashSet<String> hashSet = new HashSet<>();
                if (dfs(board,i,j,word,0,hashSet)){
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean dfs(char[][] board, int i, int j, String word,int index,HashSet<String> hashSet) {
        if (index == word.length()){
            return true;
        }
        //  边界条件
        if (i < 0 || i >= board.length || j < 0 || j >=board[i].length){
            return false;
        }
        //  这么做的原因是为了不让在深度优先遍历时“回头”
        String s1 = Integer.toString(i);
        String s2 = Integer.toString(j);
        StringBuilder ss = new StringBuilder();
        ss.append(s1);
        ss.append(s2);

        if (hashSet.contains(ss.toString())){
            return false;
        }else {
            hashSet.add(ss.toString());
        }
        if (word.charAt(index) == board[i][j]){
            boolean res =  dfs(board,i+1,j,word,index+1,hashSet) || dfs(board,i-1,j,word,index+1,hashSet)
                    || dfs(board,i,j-1,word,index+1,hashSet) || dfs(board,i,j+1,word,index+1,hashSet);
            //  注意这里撤销结果集非常重要！！！！！
            hashSet.remove(ss.toString());
            return res;
        }else {
            hashSet.remove(ss.toString());
            return false;
        }
    }
}
